package com.example.array;

/**
 * 你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。
 *  例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。
 *  但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。
 *
 *  示例 1：
 *  输入： pattern = "abba", value = "dogcatcatdog"
 * 输出： true
 *
 *  示例 2：
 *  输入： pattern = "abba", value = "dogcatcatfish"
 * 输出： false
 *
 *  示例 3：
 *  输入： pattern = "aaaa", value = "dogcatcatdog"
 * 输出： false
 *
 *  示例 4：
 *  输入： pattern = "abba", value = "dogdogdogdog"
 * 输出： true
 * 解释： "a"="dogdog",b=""，反之也符合规则
 */
public class Interview16_18_PatternMatching {
    public static void main(String[] args) {
        String pattern = "abba";
        String value = "dogcatcatdog";

//        pattern = "abba";
//        value = "dogdogdogdog";

//        pattern = "aaaa";
//        value = "dogcatcatdog";

//        pattern = "abba";
//        value = "dogcatcatfish";

        pattern = "a";
        value = "";

        pattern = "baabab";
        value = "eimmieimmieeimmiee";

        System.out.println(new Solution().patternMatching(pattern, value));
    }

    static class Solution {
        /**
         * 枚举所有可能结果进行尝试
         *
         * 首先统计pattern中'a' 'b' 的个数
         * 满足以下等式
         * aSize * aLen + bSize * bLen = value.length
         * 其中 aSize + bSize = pattern.length(aSize表示pattern中'a'出现的次数....)
         *  因为aSize、bSize是可以统计出来的
         *  因此只要枚举aLen可能的值，当aLen确定了那么当前的bLen也是确定的
         * @param pattern
         * @param value
         * @return
         */
        private boolean patternMatching1(String pattern, String value) {
            char[] patternChars = pattern.toCharArray();
            int len = value.length();
            int aSize = 0, bSize = 0;
            for (char patternChar : patternChars) {
                if (patternChar == 'a') ++aSize;
                else ++bSize;
            }
            if (patternChars.length == 0) return false;
            if (value.length() == 0 && (aSize * bSize) == 0) return true;
            int singleALenMax = aSize == 0 ? 0 : len / aSize;

            for (int aLen = 0; aLen <= singleALenMax; aLen++) { // 枚举每个可能的'a'的长度
                if (bSize != 0 && (len - aLen * aSize) % bSize != 0) continue;

                int bLen = bSize == 0 ? 0 : (len - aLen * aSize) / bSize;// 根据'a'的长度计算'b'的长度
                String tmpPatternA = "";
                String tmpPatternB = "";

                boolean res = true;
                int pos = 0;
                for (char patternChar : patternChars) {
                    if (patternChar == 'a') {
                        if (tmpPatternA.length() == 0) // 根据pattern字符串确定本次的tmpPatternA和tmpPatternB
                            tmpPatternA = value.substring(pos, pos + aLen);
                        else {
                            if (!tmpPatternA.equals(value.substring(pos, pos + aLen))) {
                                res = false;
                                break;
                            }
                        }

                        pos += aLen;
                    } else {
                        if (tmpPatternB.length() == 0) // 根据pattern字符串确定本次的tmpPatternA和tmpPatternB
                            tmpPatternB = value.substring(pos, pos + bLen);
                        else {
                            if (!tmpPatternB.equals(value.substring(pos, pos + bLen))) {
                                res = false;
                                break;
                            }
                        }

                        pos += bLen;
                    }
                }

                if (res && !tmpPatternB.equals(tmpPatternA)) {
//                    System.out.println("tmpA : " + tmpPatternA + " tmpB: " +tmpPatternB);
                    return true;
                }
            }

            return false;
        }

        public boolean patternMatching(String pattern, String value) {
            return patternMatching1(pattern, value);
        }
    }
}
